concentration inequality

Tells us how likely it is that a random variable $X$ deviates a certain amount from its expectation $\mathbb{E}[X]$.

Important tool to analyze random algorithms.

Three fundamental concentration inequalities:

1. Markov's inequality
   • applies to non-negative random values
2. Chebyshev's inequality
   • applies to random variables with bounds
3. Hoeffding inequality/Bernstein inequality/Chernoff bound ^c601f4
   • applies to sums of independent random variables

See also: concentration of chi-squared random variables, Gaussian concentration

Matrix concentration inequality

Rademacher concentration

References:

• https://ai.stanford.edu/~gwthomas/notes/concentration.html
• https://www.stat.cmu.edu/~larry/=sml/Concentration.pdf
• https://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/